package hashtable;

import java.util.Scanner;

/**
 * 哈希表
 */
public class hashtableDemo {
    public static void main(String[] args) {

        //创建一个哈希表
        HashTab hashTab = new HashTab(7);
        //写一个简单菜单
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add: 添加员工");
            System.out.println("list: 显示员工");
            System.out.println("s: 查找员工");
            System.out.println("exit: 退出系统");

            key = scanner.next().charAt(0);
            switch (key) {
                case 'a':
                    System.out.println("输入id:");
                    int id = scanner.nextInt();
                    System.out.println("输入名字：");
                    String name = scanner.next();
                    //创建员工
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;

                case 'l':
                    hashTab.list();
                    break;

                case 's':
                    System.out.println("输入id:");
                    int byid = scanner.nextInt();
                    hashTab.findEmpById(byid);
                    break;

                case 'e':
                    scanner.close();
                    System.exit(0);
                    break;
                default:
                    break;

            }
        }

    }
}

//创建一个哈希表，管理多条链表
class HashTab {
    private EmpLinkList[] empLinkListArray;
    private int size;  //表示共有多少条链表

    //构造器
    public HashTab(int size) {
        empLinkListArray = new EmpLinkList[size];
        this.size = size;

        //需要分别初始化每一条链表，否则会报空指针
        for (int i = 0; i < size; i++) {
            empLinkListArray[i] = new EmpLinkList();
        }
    }

    //添加员工
    public void add(Emp emp) {
        //根据员工的id，得到应该添加到那条链表
        int empLinkedListNO = hashFun(emp.id);
        empLinkListArray[empLinkedListNO].add(emp);

    }

    //遍历所有的链表
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkListArray[i].list(i);
        }
    }

    //根据输入的id查找员工
    public void findEmpById(int id){

        int empLinkedListNO = hashFun(id);
        Emp emp = empLinkListArray[empLinkedListNO].findEmpById(id);
        if(emp !=null){
            System.out.println("在第"+empLinkedListNO+"条链表找到该员工:=>id = "+emp.id+",name = "+emp.name);
        }else{
            System.out.println("没有找到该员工");
        }

    }

    //编写一个散列函数，取模法,找到添加位置
    public int hashFun(int id) {
        return id % size;
    }
}

//表示员工信息
class Emp{
    public int id;
    public String name;
    public Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

//创建一个EmpLinkedList，表示链表
class EmpLinkList{
    //头指针，指向第一个Emp
    private Emp head;  //默认为空

    //添加雇员到链表
    //假定就前加到最后，id是自增
    public  void add(Emp emp){

        //如果是添加第一个员工
        if(head == null){
            head = emp;
            return;
        }
        //如果不是第一个员工，则使用一个辅助指针
        Emp curEmp = head;
        while (true){
            if(curEmp.next ==null){ //说明到最后
                break;
            }
            curEmp = curEmp.next;  //否则就后移
        }
        //找到最后就直接加到最后
        curEmp.next = emp;
    }

    //遍历链表的员工信息
    public void list(int no){
        if(head == null){//说明链表为空
            System.out.println("第"+no+"条链表为空");
            return;
        }
        System.out.print("第"+no+"条链表信息为： ");
        Emp curEmp = head;
        while (true){
            System.out.printf("=> id=%d name=%s\t",curEmp.id,curEmp.name);
            if(curEmp.next == null){
                //说明到最后节点
                break;
            }
            curEmp = curEmp.next;
        }
        System.out.println("\n");
    }

    //根据id查找
    public Emp findEmpById(int id){
        //判断链表是否为空
        if(head == null){
            System.out.println("链表为空");
            return null;
        }
        Emp curEmp = head;
        while (true){
            if(curEmp.id == id){  //代表找到了
                break;
            }

            //退出条件
            if(curEmp.next == null){
                curEmp = null;
                break;
            }
            curEmp = curEmp.next; //后移
        }

        return curEmp;

    }
}
